#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class KthLargest
{
public:
    KthLargest(int k, vector<int> &nums)
    {
        fill(data, data + 20002, 0);
        int maxval = 0, cnt = k;
        for (int i : nums)
        {
            maxval = max(maxval, i + offset);
            data[i + offset]++;
        }

        for (int i = 0; i + nums.size() < k; ++i)
            data[0]++;
        ptr = maxval;
        while (cnt > 0 && data[ptr] > 0)
        {
            cnt -= data[ptr];
            while (cnt > 0 && data[--ptr] == 0);
        }
        res = data[ptr] + cnt - 1;
    }

    int add(int val)
    {
        data[val + offset]++;
        if (val + offset <= ptr)
            return ptr - offset;
        else if (res > 0)
            res--;
        else if (res == 0)
        {
            while (data[++ptr] == 0);
            res = data[ptr] - 1;
        }
        return ptr - offset;
    }

private:
    int ptr, data[20002], res = 0;
    const int offset = 10000;
};